package practice_2025_7_18;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m = 0;
    int n = 0;

    /**
     * 01矩阵
     * @param mat
     * @return
     */
    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        int[][] res = new int[m][n];
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                    res[i][j] = 0;
                    vis[i][j] = true;
                }
            }
        }
        int step = 0;
        while(!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int x = tmp[0];
                int y = tmp[1];
                for(int i = 0; i < dx.length; i++) {
                    int nextX = x + dx[i];
                    int nextY = y + dy[i];
                    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && (!vis[nextX][nextY]) && mat[nextX][nextY] == 1) {
                        vis[nextX][nextY] = true;
                        res[nextX][nextY] = step;
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
        }
        return res;
    }

    /**
     * 地图中的最高点
     * @param isWater
     * @return
     */
    public int[][] highestPeak(int[][] isWater) {
        // 0: 陆地
        // 1: 水域
        // 相邻的格子高度差至多为1
        // 要使得最高高度最大
        m = isWater.length;
        n = isWater[0].length;
        boolean[][] vis = new boolean[m][n];
        int[][] res = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        // 找到所有水域
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    vis[i][j] = true;
                    queue.add(new int[]{i, j});
                }
            }
        }
        while(!queue.isEmpty()) {
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int x = tmp[0];
                int y = tmp[1];
                for(int i = 0; i < dx.length; i++) {
                    int nextX = x + dx[i];
                    int nextY = y + dy[i];
                    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && (!vis[nextX][nextY]) && isWater[nextX][nextY] == 0) {
                        vis[nextX][nextY] = true;
                        res[nextX][nextY] = res[x][y] + 1;
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
        }
        return res;
    }

    /**
     * 地图分析
     * @param grid
     * @return
     */
    public int maxDistance(int[][] grid) {
        // 0: 海洋 1: 陆地
        // 找到一个海洋, 离它最近的陆地单元格距离最大, 并返回该距离
        // 从陆地出发, 找到最远的海洋
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        int[][] dist = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    vis[i][j] = true;
                }
            }
        }
        if (queue.isEmpty() || queue.size() == m * n) {
            return -1;
        }
        int max = 0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int x = tmp[0];
                int y = tmp[1];
                for(int i = 0; i < dx.length; i++) {
                    int nextX = x + dx[i];
                    int nextY = y + dy[i];
                    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && (!vis[nextX][nextY]) && grid[nextX][nextY] == 0) {
                        dist[nextX][nextY] = dist[x][y] + 1;
                        max = Math.max(max, dist[nextX][nextY]);
                        vis[nextX][nextY] = true;
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
        }
        return max;
    }
}
